package ArrayDemo2;

/**
 * Created by sunwei on 2017/10/13
 * Time:10:54
 */
public class OrderedArray {
    private long a[];
    private int nElems;
    /*
    构造函数
     */
    public OrderedArray(int size) {
        a = new long[size];
        nElems = 0;
    }

    /*
    设置数组大小
     */
    public int size(){
        return nElems;
    }
    /*
    向数组里面插入元素(插入时不排序)
     */
    public void notSortedInsert(long value){
        a[nElems] = value;
        nElems++;
    }

    /*
    向数组里面插入元素(插入时即排序好)
     */
    public void sortedInsert(long value){
        int j;
        //这个循环目的是，判断新添加的元素应该放在什么位置
        for(j = 0;  j<nElems ; j++) {
            if (a[j]>value) {
                  break;
            }
        }
        //找到这个位置后，将这个位置右边的元素向移动为新添加的元素腾出位置
        for(int k = nElems;k>j ;k--) {
            a[k] = a[k-1];
        }
        //腾出位置后，直接将新添加的元素放到腾出的位置上
        a[j] = value;
        //将数组元素的个数加一，每次添加一个都加一
        nElems++;
    }
    /*
    数组冒泡排序
     */
    public void bubbleSorted(){
        int in ,out;
        for(out = nElems-1;out>0 ;out--) {
            for(in = 0;in<out ;in++) {
                if (a[in]>a[in+1]) {
                      long temp;
                      temp = a[in];
                      a[in] = a[in+1];
                      a[in+1] = temp;
                }
            }
        }
    }

    /*
    插入排序
     */
    public void insertSorted(){
        int in ,out ;
        for(out = 1; out<nElems ;out++) {
            long temp = a[out];
            in = out;
            while (in>0&&a[in-1]>temp){
                a[in] = a[in-1];
                --in;
            }
            a[in] = temp;
        }
    }

    /*
    选择排序
     */
    public void selectSorted(){
        int in , out , min;
        for(out = 0;out<nElems-1 ; out++) {
            min = out;
            for( in= out+1;in<nElems ;in++) {
                if (a[min]>a[in]) {
                      min = in;
                }
            }
            long temp ;
            temp = a[min];
            a[min] = a[out];
            a[out] = temp;
        }
    }

    /*
    用二分法进行查找数组里面的元素
     */
    public int find(long searchKey){
        int lowerBound = 0;
        int upperBound = nElems-1;
        int middle;
        //二分法循环查找输入的元素，每次查找一遍查找的范围都会减半，直到lowerBound得值大于upperBound的值
        while (true){
            middle = (lowerBound+upperBound)/2;
            if (a[middle]==searchKey) {
                  return middle;
            }  else if (lowerBound>upperBound) {
                  return nElems;
            }  else {
                if (a[middle]<searchKey) {
                      lowerBound = middle +1;
                }  else {
                    upperBound = middle-1;
                }
            }
        }
    }

    public boolean delete(long value){
        int j;
        if (find(value)== nElems) {
              return false;
        }else {
            for(int k = find(value);k<nElems ; k++) {
                a[k] = a[k+1];
            }
            nElems--;
            return true;
        }
    }

    /*
    遍历显示数组
     */
    public void display(){
        for(int j = 0; j <nElems ; j++) {
            System.out.print(a[j]+ " ");
        }
    }

}
